5E - Bindian Signalizing - CodeForces Solution

data structures *2400

Please click on ads to support us..

Python Code: 

n = int(input())
arr = [*map(int,input().split())]
i = arr.index(max(arr))
arr = arr[i:]+arr[:i]

stack,res = [[arr[0],1]],0
for j in range(1,n):
    if arr[j]>stack[-1][0]:
        while stack[-1][0]<arr[j]:
            res += stack.pop()[1]
    if arr[j]<stack[-1][0]: res += 1; stack += [arr[j],1],
    elif arr[j]==stack[-1][0]: res += stack[-1][1]+(len(stack)>1); stack[-1][1] += 1

if len(stack)>1 and stack[0][1]>1: res += stack[1][1]
for j in range(2,len(stack)): res += stack[j][1]
print(res)

C++ Code: 

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
int a[maxn], b[maxn], l[maxn], r[maxn], s[maxn];

int main() {
    int n, maxn, po;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    maxn = a[0];
    po = 0;

    for (int i = 1; i < n; i++) {
        if (a[i] > maxn) {
            maxn = a[i];
            po = i;
        }
    }

    for (int i = 0; i < n; i++)
        b[i] = a[(po + i) % n];
    
    b[n] = b[0];
    s[n] = 0;
    
    for (int i = n - 1; i >= 0; i--) {
        r[i] = i + 1;

        while (r[i] < n && b[i] > b[r[i]])
            r[i] = r[r[i]];
        
        while (r[i] < n && b[i] == b[r[i]]) {
            s[i] = s[r[i]] + 1;
            r[i] = r[r[i]];
        }
    }

    l[0] = 0;
    
    for (int i = 1; i < n; i++) {
        l[i] = i - 1;

        while (l[i] > 0 && b[i] >= b[l[i]])
            l[i] = l[l[i]];
    }

    long long ans = 0;
    
    for (int i = 0; i < n; i++) {
        ans += s[i];

        if (b[i] < b[0]) {
            if (l[i] == 0 && r[i] == n) ans += 1;
            else ans += 2;
        }
    }

    cout << ans;

    return 0;
}


Comments

Submit
0 Comments
More Questions

721B - Passwords
1263D - Secret Passwords
1371B - Magical Calendar
1726E - Almost Perfect
1360C - Similar Pairs
900A - Find Extra One
1093D - Beautiful Graph
748A - Santa Claus and a Place in a Class
1511B - GCD Length
676B - Pyramid of Glasses
597A - Divisibility
1632A - ABC
1619D - New Year's Problem
242B - Big Segment
938A - Word Correction
159C - String Manipulation 10
258A - Little Elephant and Bits
1536C - Diluc and Kaeya
1428C - ABBB
1557A - Ezzat and Two Subsequences
255A - Greg's Workout
1059A - Cashier
1389C - Good String
1561A - Simply Strange Sort
1337B - Kana and Dragon Quest game
137C - History
1443C - The Delivery Dilemma
6C - Alice Bob and Chocolate
1077C - Good Array
285B - Find Marble